package main

import (
	"fmt"
	"sort"
)

//hashMap这里不再展示
//遍历获取1的个数，并除以3取余:24ms 58%, 6.3MB 38%
func singleNumber(nums []int) int {
	oneNums := make([]int, 31)
	for _, v := range nums {
		for i := 0; v > 0; i++ {
			oneNums[i] += v & 1
			v >>= 1
		}
	}
	res := 0
	for i, v := range oneNums {
		res += (v % 3) * (1 << i)
	}
	return res
}

//排序:24ms 58%, 6.3MB 38%
func singleNumber1(nums []int) int {
	sort.Ints(nums)
	if nums[0] != nums[1] {
		return nums[0]
	}
	if nums[len(nums)-1] != nums[len(nums)-2] {
		return nums[len(nums)-1]
	}
	for i := 1; i < len(nums)-1; i++ {
		if nums[i] != nums[i-1] && nums[i] != nums[i+1] {
			return nums[i]
		}
	}
	return 0
}

func main() {
	fmt.Println(singleNumber([]int{1, 2, 2, 2}))
	fmt.Println(singleNumber1([]int{1, 2, 2, 2}))
}
